package binaryTree;


import org.junit.Test;

//求二叉树的最大距离问题
public class LeetCode_543 {

    @Test
    public void test(){
        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        root.left.left.left = new TreeNode(6);
        root.left.left.left.left = new TreeNode(9);
        root.left.right.left= new TreeNode(7);
        root.left.right.right = new TreeNode(8);
        root.left.right.left.left = new TreeNode(10);

        System.out.println("最大距离："+diameterOfBinaryTree(root));
    }


    public int diameterOfBinaryTree(TreeNode root) {
        return getMaxDistance(root).currentMaxDis;
    }

    //返回值类型
    public class Info{
        int leftHeight;     //左树高
        int rightHeight;    //右树高
        int currentMaxDis;  //当前的最大距离

        public Info(int leftHeight, int rightHeight, int currentMaxDis) {
            this.leftHeight = leftHeight;
            this.rightHeight = rightHeight;
            this.currentMaxDis = currentMaxDis;
        }
    }

    //节点
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 获得最大距离
     * @param root 根节点
     * @return
     */
    public Info getMaxDistance(TreeNode root){
        //1. 终止条件
        if (root == null){
            return new Info(0,0,0);
        }
        //2. 判断
        //2.1 获得左树info
        Info leftInfo = null;
        if (root.left!=null){
            leftInfo = getMaxDistance(root.left);
        }
        //2.2 获得右树info
        Info rightInfo = null;
        if (root.right!=null){
            rightInfo = getMaxDistance(root.right);
        }
        //2.3 计算当前节点的info信息
        int currentMaxDis = 0;
        int leftHeight = 0;
        int rightHeight = 0;
        //2.3.1 左右子树高度
        if (leftInfo!=null){
            leftHeight = Math.max(leftInfo.leftHeight, leftInfo.rightHeight) + 1;
        }
        if (rightInfo!=null){
            rightHeight = Math.max(rightInfo.leftHeight, rightInfo.rightHeight) + 1;
        }
        //2.3.2 计算当前节点的最大距离
        if (leftInfo!=null){
            currentMaxDis = Math.max(leftHeight + rightHeight , leftInfo.currentMaxDis);
        }
        if (rightInfo!=null){
            currentMaxDis = Math.max(Math.max(leftHeight + rightHeight, rightInfo.currentMaxDis), currentMaxDis);
        }

        //3. 返回结果
        return new Info(leftHeight, rightHeight, currentMaxDis);
    }




}
